package com.fengye.algorithms.leecode.dp;

/**
 * @Author fengye
 * @Date 2023/5/2 10:08
 **/
public class UniquePaths62 {
    public static void main(String[] args) {
        System.out.println(new UniquePaths62().uniquePaths1(51,9));
    }

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        // 第一列
        for(int i=0;i<m;i++) {
            dp[i][0] = 1;
        }
        // 第一行
        for(int j=0;j<n;j++) {
            dp[0][j] = 1;
        }

        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

    /**
     * 会超时
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths1(int m, int n) {
        if( n==1 || m==1) {
            return 1;
        }

        return uniquePaths1(m-1, n) + uniquePaths(m, n-1);
    }
}
